home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 01 Manslow / GAPBILExample / CPS.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-10-10  |  7.8 KB  |  305 lines
  1. //GAPBILExample
  2. //Copyright John Manslow
  3. //29/09/2001
  4.  
  5. ////////////////////////////////////////////////////
  6. //Remove this include if not compiling under Windows
  7. #include "stdafx.h"
  8. #define new DEBUG_NEW
  9. ////////////////////////////////////////////////////
  10.  
  11. #include "CPS.h"
  12. #include "assert.h"
  13. #include "fstream.h"
  14.  
  15. CPS::CPS(
  16.          const unsigned long    ulNewChromosomeLength,
  17.          const int * const            pnNewGeneTypes
  18.          )
  19. {
  20.     unsigned long i;
  21.  
  22.     //Use asserrts to check the validity of the parameters
  23.     assert(!(ulNewChromosomeLength<1));
  24.     ulChromosomeLength=ulNewChromosomeLength;
  25.  
  26.     //The default initial values for the mutation rate and step size are quite large to allow
  27.     //the search to be quite broad at the start. This makes sense because at the start of the
  28.     //search any behaviours we discover are likely to be poor, so we want to spend most 
  29.     //of our time exploring new ones. These values may need to be changed for different
  30.     //applications (particularly the initial step size)
  31.     dMutationRate=0.5;
  32.     dStepSize=0.5;
  33.  
  34.     //Allocate memory.
  35.     AllocateMemory();
  36.  
  37.     //Record the types of each gene
  38.     for (i=0;i<ulChromosomeLength;i++)
  39.     {
  40.         pnGeneTypes[i]=pnNewGeneTypes[i];
  41.     }
  42.  
  43.     //And initialise the search with a random chromosome
  44.     InitialisePopulation();
  45. }
  46.  
  47. CPS::~CPS()
  48. {
  49.     //Deallocate memory!
  50.     DeallocateMemory();
  51. }
  52.  
  53. void CPS::AllocateMemory(void)
  54. {
  55.     //An array to store the type of each gene. Genes can be either binary (type 0) or real (type 1)
  56.     pnGeneTypes=new int[ulChromosomeLength];
  57.  
  58.     //A place to store the working chromosome (that which is having its fitness evaluated)
  59.     pdGenes=new double[ulChromosomeLength];
  60.  
  61.     //Space to store a copy of the best chromosome found so far
  62.     pdBestChromosome=new double[ulChromosomeLength];
  63. }
  64.  
  65. void CPS::DeallocateMemory(void)
  66. {
  67.     //Deallocate everything
  68.     delete []pnGeneTypes;
  69.     delete []pdBestChromosome;
  70.     delete []pdGenes;
  71. }
  72.  
  73. void CPS::InitialisePopulation(void)
  74. {
  75.     unsigned long i;
  76.  
  77.     //Since this restarts the search, we might as well reset the iteration counter
  78.     ulIteration=0;
  79.  
  80.     //Also set the best fitness to a large negative value so that it will be overwritten immediately. Of
  81.     //course, make sure that no fitness evaluations can result in fitnesses more negative than this
  82.     dBestFitness=-1e+100;
  83.  
  84.     //Initialise the best and working chromosomes and the fitness statistics
  85.     //Sets the genes of the ith chromosome to random values
  86.     for (i=0;i<ulChromosomeLength;i++)
  87.     {
  88.         if(pnGeneTypes[i]==0)
  89.         {
  90.             //If this gene is binary set it to either 0 or 1
  91.             pdGenes[i]=double(rand()%2);
  92.         }
  93.         else
  94.         {
  95.             //Otherwise, set it to a random value between 0 and 1
  96.             pdGenes[i]=double(rand())/double(RAND_MAX);
  97.         }
  98.         pdBestChromosome[i]=pdGenes[i];
  99.     }
  100. }
  101.  
  102. void CPS::Mutate(void)
  103. {
  104.     unsigned long i;
  105.  
  106.     //Make sure the argument is valid
  107.     assert(pdGenes);
  108.  
  109.     //For every gene in the chromosome
  110.     for (i=0;i<ulChromosomeLength;i++)
  111.     {
  112.         //Is the gene binary?
  113.         if(pnGeneTypes[i]==0)
  114.         {
  115.             //If so, mutate it with probability dMutationRate
  116.             if(double(rand())/double(RAND_MAX)<dMutationRate)
  117.             {
  118.                 pdGenes[i]=1.0-pdGenes[i];
  119.             }
  120.         }
  121.         else
  122.         {
  123.             //Otherwise, perturb it with a random value between -dStepSize and +dStepSize
  124.             pdGenes[i]=2.0*(double(rand())/double(RAND_MAX)-0.5)*dStepSize;
  125.         }
  126.     }
  127. }
  128.  
  129. double *CPS::pdGetChromosomeForEvaluation(void)
  130. {
  131.     //This and SetFitness are the only functions that need to be called to make the search work.
  132.     unsigned long i;
  133.  
  134.     //Prepare some storage for a copy of the new chromosome so that it can be returned to the calling
  135.     //function and its fitness evaluated
  136.     double *pdChromosomeForEvaluation=new double[ulChromosomeLength];
  137.     for (i=0;i<ulChromosomeLength;i++)
  138.     {
  139.         //Copy the best chromosome into the working chromosome
  140.         pdGenes[i]=pdBestChromosome[i];
  141.     }
  142.  
  143.     //Mutate the working chromosome
  144.     Mutate();
  145.  
  146.     for (i=0;i<ulChromosomeLength;i++)
  147.     {
  148.         //And make a copy of it so that its fitness can be evaluated
  149.         pdChromosomeForEvaluation[i]=pdGenes[i];
  150.     }
  151.  
  152.     //Return it
  153.     return pdChromosomeForEvaluation;
  154. }
  155.     
  156. void CPS::SetFitness(const double dNewFitness)
  157. {
  158.     //This is the only other function that needs to be called and is used to set the fitness of a chromosome
  159.     //that has just been evaluated
  160.  
  161.     //The following line could be made stachastic (resulting in an algorithm similar to 
  162.     //simulated annealing (SA). If the fitness is higher than anything yet achieved:
  163.     if(dNewFitness>=dBestFitness)
  164.     {
  165.         //Record it
  166.         dBestFitness=dNewFitness;
  167.  
  168.         //And keep a copy of the chromosome
  169.         unsigned long i;
  170.         for(i=0;i<ulChromosomeLength;i++)
  171.         {
  172.             pdBestChromosome[i]=pdGenes[i];
  173.         }
  174.  
  175.         //Increase the scope of the search a little
  176.         dStepSize*=1.2;
  177.         dMutationRate*=1.2;
  178.  
  179.         //The largest meaningful value for the mutation probability is 0.5
  180.         if(dMutationRate>0.5)
  181.         {
  182.             dMutationRate=0.5;
  183.         }
  184.  
  185.         //Stop the mutation rate dropping too low. Because the search is mutation based,
  186.         //it ends if the mutation rate drops too low, because the agent spends all its time
  187.         //exploiting the best behaviour it has discovered and spends no time exploring 
  188.         //alternatives
  189.         if(dMutationRate<0.5/double(ulChromosomeLength))
  190.         {
  191.             dMutationRate=0.5/double(ulChromosomeLength);
  192.         }
  193.     }
  194.     else
  195.     {
  196.         //If this behaviour was not at least as good as the best, reduce the breadth of the
  197.         //search a little because the behaviours we're trying may be too different. The 
  198.         //multipliers in these lines and those above control the rate of convergence of the 
  199.         //algorithms and set the trade-off between exploration and exploitation. Setting the
  200.         //constants below to be very small (which, in this case would mean 0.9, say) would
  201.         //make the algorithm converge very rapidly and the agent would spend its time
  202.         //exploiting a very poor behaviour because it hasn't adequately explored. Setting the 
  203.         //constants above (which are 1.2 by default) to be too large (say, 10) would make 
  204.         //the agent spent a lot of time exploring radical behaviours that are so different to
  205.         //what actually wroks that its average performance would be very poor
  206.         dStepSize*=0.99;
  207.         dMutationRate*=0.99;
  208.     }
  209.  
  210.     //Record another fitness evaluation
  211.     ulIteration++;
  212. }
  213.  
  214. double *CPS::pdGetBestChromosome(void)
  215. {
  216.     //Returns a pointer to the best chromosome discovered so far. Don't delete!
  217.     return pdBestChromosome;
  218. }
  219.  
  220. double CPS::dGetBestPerformance(void)
  221. {
  222.     //Return the best fitness achieved so far
  223.     return dBestFitness;
  224. }
  225.  
  226. int CPS::Save(const char * const psFilename)
  227. {
  228.     //Saves the status of the search
  229.     ofstream *pOut=new ofstream(psFilename);
  230.     unsigned long i,j;
  231.     if(!pOut || !pOut->is_open())
  232.     {
  233.         return 0;
  234.     }
  235.     pOut->precision(18);
  236.     *pOut<<ulChromosomeLength;
  237.     *pOut<<"\n";
  238.     *pOut<<dMutationRate;
  239.     *pOut<<"\n";
  240.     *pOut<<dStepSize;
  241.     *pOut<<"\n";
  242.     *pOut<<ulIteration;
  243.     *pOut<<"\n";
  244.     for (i=0;i<ulChromosomeLength;i++)
  245.     {
  246.         *pOut<<pnGeneTypes[i];
  247.         *pOut<<"\t";
  248.     }
  249.     *pOut<<"\n";
  250.     for (i=0;i<ulChromosomeLength;i++)
  251.     {
  252.         *pOut<<pdGenes[i];
  253.         *pOut<<"\t";
  254.     }
  255.     *pOut<<dBestFitness;
  256.     *pOut<<"\n";
  257.     for (j=0;j<ulChromosomeLength;j++)
  258.     {
  259.         *pOut<<pdBestChromosome[j];
  260.         *pOut<<"\t";
  261.     }
  262.     *pOut<<"\n";
  263.     pOut->close();
  264.     delete pOut;
  265.     return 1;
  266. }
  267.  
  268. int CPS::Load(const char * const psFilename)
  269. {
  270.     //And load it!
  271.     ifstream *pIn=new ifstream(psFilename,ios::nocreate);
  272.     unsigned long i,j;
  273.     if(!pIn || !pIn->is_open())
  274.     {
  275.         return 0;
  276.     }
  277.  
  278.     //Free up memory used by the algorithm as it is now
  279.     DeallocateMemory();
  280.  
  281.     *pIn>>ulChromosomeLength;
  282.  
  283.     //Allocate new memory
  284.     AllocateMemory();
  285.     *pIn>>dMutationRate;
  286.     *pIn>>dStepSize;
  287.     *pIn>>ulIteration;
  288.     for (i=0;i<ulChromosomeLength;i++)
  289.     {
  290.         *pIn>>pnGeneTypes[i];
  291.     }
  292.     for (i=0;i<ulChromosomeLength;i++)
  293.     {
  294.         *pIn>>pdGenes[i];
  295.     }
  296.     *pIn>>dBestFitness;
  297.     for (j=0;j<ulChromosomeLength;j++)
  298.     {
  299.         *pIn>>pdBestChromosome[j];
  300.     }
  301.     pIn->close();
  302.     delete pIn;
  303.     return 1;
  304. }
  305.